星尘

15. 三数之和

发表于 更新于 分类于

15. 三数之和

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1:

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2:

1
2
输入：nums = []
输出：[]

示例 3:

1
2
输入：nums = [0]
输出：[]

题解

  1. 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []

  2. 然后对数据进行从小到大的排序

  3. 左指针 = 当前值下标 + 1，左指针 = 数组长度 - 1。只要左指针没有超过右指针，那么就一直循环：

    计算 “当前值 + 左指针位置的元素值 + 右指针位置的元素值‘’。

    如果和值大于0，那么右指针需要左移(将和值减小)。

    如果和值小于0，那么左指针需要右移(将和值增大)。

    如果和值等于0，那么需要判断左右边界是否和下一位值相同，相同则需要再次移动一步，目的是为了去除重复的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def threeSum(self, nums):
        result = []

        # 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []
        if len(nums) < 3:
            return []

        size = len(nums)
        nums.sort()

        for i, v in enumerate(nums):
            # 判断当前值是否和上一位值是否重复，重复的就跳过，目的是为了去除重复解
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = size - 1

            # 只要左指针没有超过右指针，那么就一直循环
            while left < right:
                sum_value = v + nums[left] + nums[right]
                if sum_value > 0:
                    # 和值大于0, 右指针需要左移
                    right -= 1
                elif sum_value < 0:
                    # 和值小于0, 左指针需要右移
                    left += 1
                else:
                    result.append([v, nums[left], nums[right]])
                    # 判断左边界和右边界是否和下一位值重复，目的是为了去除重复解
                    while left != right and nums[left] == nums[left + 1]:
                        left += 1
                    while left != right and nums[right] == nums[right - 1]:
                        right -= 1
                    # 最后左右指针各移动一步
                    right -= 1
                    left += 1
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func threeSum(nums []int) [][]int {
	var result [][]int

	if len(nums) < 3{
		return result
	}

	size := len(nums)
	sort.Ints(nums)

	for i, v:= range nums{
		if i > 0 && nums[i] == nums[i-1]{
			continue
		}

		left := i +1
		right := size - 1

		for left < right{
			sumValue := v + nums[left] + nums[right]
			if sumValue >0{
				right -=1
			}else if sumValue < 0 {
				left += 1
			}else{
				result = append(result, []int{v, nums[left], nums[right]})

				for left != right && nums[left] == nums[left+1]{
					left += 1
				}
				for left != right && nums[right] == nums[right-1]{
					right -=1
				}
				left +=1
				right -=1
			}
		}
	}
	return result
}

变体

总结

参考

1
2